1. Field of the Invention
The present invention relates to data networking and specifically to avoiding micro-loops in a data network employing protected links.
2. Background Information
A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end stations, such as computers. Many types of network segments are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect personal computers and workstations over dedicated, private communications links located in the same general physical location, such as a building or a campus. LANs may also connect routers co-located within a close range.
WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Certain nodes, such as routers, are often configured to “route” data, such as packets, between various nodes in the network. Routing is typically performed at the network layer or layer-3 (L3) of the Open Systems Interconnect (OSI) Reference Model. Routers often maintain forwarding databases (FDBs), which are typically configured to hold routing information including L3 addresses and interface information that the router uses to determine where data (e.g., data packets) are to be forwarded in order to reach their destination. For example, a router may have a routing database containing one or more entries wherein each entry contains a L3 destination address of a destination node and interface information about an interface on the router through which the destination node may be reached. A data packet containing a destination address that matches a destination address of an entry in the routing table is forwarded by the router to the interface specified by the matching entry for transfer to the destination node.
A router may execute one or more routing protocols that enable the router to route packets and exchange routing information with other routers in the network. The routers often use this information to configure (e.g., compute) their FDBs. The routing protocols may include distance vector protocols, such as the Routing Information Protocol (RIP) or link-state protocols, such as the Intermediate-System-to-Intermediate-System (IS-IS) protocol or the Open Shortest Path First (OSPF) protocol. Routing information is typically exchanged between the routers in the form of advertisement messages. For example, nodes executing the IS-IS protocol exchange information using an advertisement message called a Link State Packet (LSP). Likewise, nodes executing the OSPF protocol exchange routing information using an advertisement message called a Link State Advertisement (LSA). As used herein, an advertisement message refers generically to a message that a routing protocol uses to convey routing information to other intermediate nodes (e.g., a router, a switch) in the network. An intermediate node that acquires an advertisement message may use information contained therein to update its FDB.
Routers may transfer data packets through the network between a source and destination in a “connection-oriented” manner using a connection-oriented protocol. A connection-oriented protocol transfers data packets through the network over a predefined path, often called a connection or circuit, that is established between the source and destination. Here, the connection or circuit is established between the source and destination before any data are transferred. After the connection has been established, data are transferred between the source and destination over a path defined by the connection. When the connection is no longer needed, the connection is typically “torn down” and resources, such as nodes, interfaces, protocols and so on, utilized by the connection are made available for other connections. An example of a connection-oriented protocol is the Multiprotocol Label Switching (MPLS) protocol. A resource, as used herein, refers to entities associated with an intermediate node. These entities may include the intermediate node itself, an interface (e.g., a port) on the intermediate node and a protocol running on the intermediate node.
Some connection-oriented protocols utilize unidirectional connections, i.e., connections that transfer data in one direction from a source to a destination. For example, a unidirectional connection between a router A and a router B transfers data in one direction from router A to router B. In order to transfer data in the other direction, i.e., from router B to router A, another unidirectional connection from router B to router A would have to be established. The connections may be “signaled” end-to-end using a signaling protocol, such as the Resource Reservation Protocol (RSVP). The end of the connection that initiates the signaling for the connection is often called the “head-end” of the connection and the end of the connection that terminates the signaling is often called the “tail-end” of the connection. The router hosting the head-end of the connection is often called the head-end node and the router hosting the tail-end of the connection is often called the tail-end node. Thus, for example, in a connection from a source to a destination where router A hosts the “head-end” of the connection and router B hosts the tail-end of the connection, router A is the head-end node and router B is the tail-end node.
To accommodate high availability, some connection-oriented protocols may include techniques that enable primary paths carrying connections to be quickly rerouted in the event that the primary path contains a failed link. For example, P. Pan, et al., “Fast Reroute Extensions to RSVP-TE for LSP Tunnels,” draft-ietf-mpls-rsvp-fastreroute-04.txt, available from the Internet Engineering Task Force (IETF), describes a MPLS “fast reroute” (FRR) technique that may be used to quickly reroute around failed network elements (e.g., link, node) in a MPLS label-switched path. According to the technique, one or more links in the primary path are protected links (i.e., they are protected by an alternate path). If a failure occurs on a protected link or node, traffic carried on Traffic Engineering MPLS Label Switch Paths (TE LSPs) is locally rerouted onto e.g., an appropriate alternate path by the node immediately upstream from the failure. The alternate path acts as a FRR for the primary label-switched path and obviates having to resort to other perhaps costlier measures, such as tearing down the primary label-switched path and establishing a new primary label-switched path around the failed network element. Note that, a local reroute may be followed by an end-to-end re-optimization triggered by a head-end label-switched router (LSR) in order to cause the traffic to follow a more optimal label-switched path.
One problem with FRR techniques is that their advantages (e.g., the ability to quickly reroute around a failure) may be diminished due to e.g., micro-loops that may develop as a consequence of intermediate nodes responding to a failed link. For example, in an IP network, micro-loops typically occur due to differences in the time it takes for the intermediate nodes to recalculate their FDBs in response to the failed protected link. FIG. 1 illustrates an IP data network 100 comprising end nodes 120a-b coupled through data network 100 via various intermediate nodes 110a-d and data links 130a-f. Assume link 130c is a protected link that is associated with a alternate path to node 110c via nodes 110b, 110a and 110d. Further assume that a primary path extends from end node 120a to end node 120b via nodes 110a, 110b and 110c. Now assume link 130c fails and intermediate node 110b has detected the link failure and recalculated its FDB to direct traffic destined for end node 120b to the alternate path. Further assume intermediate node 110a has not recalculated its FDB to account for the failed link 130c and, thus, continues to forward data destined for end node 120b on the primary path. Data destined for end node 120b is forwarded by intermediate node 110a to intermediate node 110b which, in turn, forwards the data onto the alternate path to intermediate node 110a. Since it has not updated its FDB to account for the failed link 130c, intermediate node 110a forwards the data back to intermediate node 110b. Hence, a micro-loop between nodes 110a and 110b is formed. This micro-loop persists until intermediate node 110a updates its FDB to account for the failed link 130c. 
In a typical network arrangement, the amount of time involved to switch from a primary path to an alternate path in a FRR scheme may be on the order of tens of milliseconds. On the other hand, the time it takes for intermediate nodes in a network to converge their FDBs to a network topology may take on the order of many hundreds of milliseconds. The convergence process may be further delayed due to micro-loops that may form at various points in the network while the intermediate nodes converge their FDBs to the network topology. During the time the intermediate nodes are converging their FDBs the network may be unavailable. This acts to diminish the value of fast rerouting (i.e., the ability to switch from a primary path to an alternate path quickly). Even though switching from a primary path to an alternate path in a FRR implementation may have occurred quickly (e.g., in tens of milliseconds), the alternative path may be unusable for perhaps hundreds of milliseconds due to e.g., network outages caused by FDB convergence further aggravated by the occurrence of micro-loops.